#pragma once

template <class TYPE>
class List
{
public:
/**
	* @param a_index which value to change
	* @param a_value what to change the value to
	*/
	virtual void set(int const & a_index, TYPE const & a_value) = 0;
	/** @return the value at the given index */
	virtual TYPE & get(int const & a_index) const = 0;
	/** @return first index with the given value */
	virtual const int indexOf(TYPE const & a_value) const= 0;
	/** orders the list so that get(N) < get(N+1) */
	virtual void sort() = 0;
	/** @return the number of values in the list */
	virtual const int getSize() const = 0;
	/** make room at the given index for the given value */
	virtual void insert(int const & a_index, TYPE const & a_value) = 0;
	/** removes an element from the list at the given index */
	virtual void remove(TYPE const & a_index) = 0;
};

template <class TYPE>
class Vector : public List<TYPE>
{
private:
	TYPE * m_ptr;
	int m_size;
	int m_allocated;
public:
	Vector():m_ptr(NULL),m_allocated(0),m_size(0){}

	~Vector()
	{
		if(m_ptr)
			delete m_ptr;
		m_ptr = 0;
		m_allocated = 0;
		m_size = 0;
	}

	inline void Init(){
		m_ptr = NULL;
		m_allocated = 0;
		m_size = 0;
		//ensureCapacity();
	}

	/* deletes the entire structure **/
	inline void Clear()
	{
		delete [] m_ptr;
		m_ptr = NULL;
		m_size = 0;
		m_allocated = 0;
	}

	inline void ensureCapacity(int const & a_size)
	{
		// if we have no array
		if(m_ptr == NULL){
			// make an array
			m_allocated = 5;
			m_ptr = new TYPE[m_allocated];
		}
		// if our array is not big enough
		if(a_size >= m_allocated){
			// make a bigger array
			int biggerArraySize = m_allocated+5;
			TYPE * biggerArray = new TYPE [biggerArraySize];
			// copy the old values into the new array
			for(int i = 0; i < m_allocated; ++i)
			{
				biggerArray[i] = m_ptr[i];
			}
			// delete the old array
			delete [] m_ptr;
			// make the ptr point at the new array
			m_ptr = biggerArray;
			m_allocated = biggerArraySize;
		}
	}

	inline void set(int const & a_index, TYPE const & a_value)
	{
		m_ptr[a_index] = a_value;
	}

	inline TYPE & get(int const & a_index) const
	{
		return m_ptr[a_index];
	}

	inline const int indexOf(TYPE const & a_value) const
	{
		for(int i = 0; i < m_size; i++)
		{
			if(get(i) == a_value)
				return i;
		}
		return -1;
	}

	inline void add(TYPE const & a_value)
	{
		// make sure we have enough array to add to
		ensureCapacity(m_size+1);
		// add to the array
		m_ptr[m_size++] = a_value;
	}

	inline void sort()
	{
		for(int j = 1; j < m_size; ++j)
		{
			TYPE key = m_ptr[j];
			int i = j - 1;
			while(i >= 0 && m_ptr[i] > key)
			{
				m_ptr[i+1] = m_ptr[i];
				i--;
			}
			m_ptr[i+1] = key;
		}
	}

	inline const int getSize() const
	{
		return m_size;
	}

	inline bool empty()
	{
		if(m_size<=0)
			return true;
		else return false;
	}

	inline void insert(int const & a_index, TYPE const & a_value)
	{
		// what if there is not enough to insert?
		ensureCapacity(m_size+1);
		// shift all of the elements over
		for(int i = m_size; i > a_index; --i)
		{
			m_ptr[i] = m_ptr[i-1];
		}
		// put the new element in its spot
		m_ptr[a_index] = a_value;
		m_size++;
	}

	inline void remove(TYPE const & a_value)
	{	
		bool Found = false;
		int j = 0;
		for(int i = 0; i < m_size; ++i)
		{
			if(a_value == m_ptr[i])
			{
				if(!Found)
				{
					Found = true;
					j = i;
				}
			}
		}
		if(Found)
		{
			m_size--;
			for(int i = j; i < m_size; ++i)
			{
				m_ptr[i] = m_ptr[i+1];
			}
		}
	}

	inline void AddVector(Vector<TYPE> &V)
	{
		for(int i = 0;i < V.getSize();++i)
		{
			add(V.get(i));
		}
	}
};